The Halting Theorem

By Jack Copeland

© Copyright B.J. Copeland, May 2000

The Halting Theorem concerns what I will call the 'terminating program task' or 'TP task'.

This task is to respond in accordance with the following rules to inputs of arbitrarily selected finite strings of binary digits:

(1) Answer '1' if the input string is a program that will cause the universal Turing machine to execute only a finite number of actions. (Such programs are called 'terminating'.)

(2) Answer '0' if the string is not a terminating program - i.e. if the string is either a Turing machine program that does not terminate or is not a well-formed Turing machine program at all.

An example of a terminating program is one for finding the highest factor of a given integer, terminating on producing the answer. An example of a non-terminating program is one for calculating the digits of p (p having no last digit).

The Halting Theorem says this: a finitely-operating universal Turing machine cannot carry out the TP task.

A finitely-operating machine is one that delivers each of its answers after carrying out only a finite number of atomic operations.

The modern computer is based on the universal Turing machine. Since a finitely-operating universal Turing machine cannot carry out the TP task, nor can your computer. Indeed, even if your computer (or anyone else's computer) were given unlimited amounts of memory, and were allowed unlimited amounts of time in which to carry out an unlimited (although always finite) number of computations, your computer would still not be able to carry out the TP task.

The TP task is a variation on a task invented by Turing in his 1936 article 'On Computable Numbers, with an Application to the Entscheidungsproblem'. In this article Turing stated and proved a theorem similar to the Halting Theorem.